package com.da.javatest.leetCode;

import java.util.Collections;
import java.util.List;

/**
 * @author chenlida
 * @date 2019/1/8 16:18
 * @description
 */
public class Code120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        for (int i = 1; i < triangle.size(); i++) {
            List<Integer> r = triangle.get(i);
            for (int j = 0; j < r.size(); j++) {
                if (j == 0) {
                    r.set(j, r.get(j) + triangle.get(i - 1).get(j));
                } else if (j == r.size() - 1) {
                    r.set(j, r.get(j) + triangle.get(i - 1).get(j - 1));
                } else {
                    r.set(j, r.get(j) + Math.min(triangle.get(i - 1).get(j - 1), triangle.get(i - 1).get(j)));
                }
            }
        }
        Collections.sort(triangle.get(triangle.size() - 1));
        return triangle.get(triangle.size() - 1).get(0);
    }
}
